/*
 * main.c
 *  Created on: 2015-12-16
 *      Author: ZhaoYueNing
 *      git_osc:http://git.oschina.net/Buynow96/C-code
 *      数据结构实验 双链表 插入 删除 搜索 正序 反序遍历
 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/**
 * 学生结构体
 * 学生的名字和年龄
 * 前后节点的引用
 */
typedef struct STU STU;
struct STU {
    char name[20];
    int age;
    struct STU* next;
	struct STU* prev;
}*first, *p, *last;


/////////////////////////////////////////////////////////////////
//API
/////////////////////////////////////////////////////////////////

int initTable();					//初始化链表
void addInfo();						//为p指向的节点输入数据
void printNode(STU* p);				//输出p指向的节点信息
void printTable();					//以正序或者逆序输出整个链表
void findNode();					//通过搜索姓名或年龄来匹配节点
STU* returnNode(int n);				//返回第n个位置的节点的引用
void deleteNode();					//删除一个指定位置的节点
void addNode();						//添加一个指定位置的节点

int amount;

/////////////////////////////////////////////////////////////////
//Main
/////////////////////////////////////////////////////////////////
int main() {
	amount=initTable();				//初始化链表并获得节点数
	printTable();
	findNode();
	deleteNode();
	addNode();
	printTable();

	return 0;
}


/**
 * 初始化链表
 */
int initTable() {
	int amount = 0;						//节点的数量

	char opt='y';							//用户选择是否继续字符
	while (opt != 'n' && opt != 'N') {
	if(amount==0){
										//写入链表的头节点
		first = p = last = (STU*) malloc(sizeof(STU));
		p->next = p->prev = NULL;
	}else{
		p=(STU*)malloc(sizeof(STU));
		p->prev=last;
		last->next=p;
		p->next=NULL;
		last=p;
	}
	addInfo();
	amount++;
	printf("是否继续添加学生信息 结束添加请输入N:");
	scanf("%c", &opt);					//询问是否继续添加节点
	}
	return amount;
}
/**
 * 输出链表
 */
void printTable(){
	int opt;
	printf("1.正序遍历\n2.逆序遍历\n选择遍历方式:");
	scanf("%d",&opt);
	if(opt==1){
		p=first;
		while(p!=NULL){
			printNode(p);
			p=p->next;
		}
	}else if(opt==2){
		p=last;
		while(p!=NULL){
			printNode(p);
			p=p->prev;
		}
	}
}
/**
 * 添加单个学生信息到指针p
 */
void addInfo() {
	printf("请输入学生姓名:");
	scanf("%s", p->name);
	printf("请输入学生年龄:");
	scanf("%d", &p->age);
	getchar();							//去除缓冲区
}
/**
 * 输出单个节点p的信息
 */
void printNode(STU* p){
	printf("学生姓名:%s",p->name);
	printf("\t学生年龄:%d\n",p->age);
}

/**
 * 搜索学生节点
 */
void findNode(){
	p=first;
	int opt;
	int fAge;
	int n;							//匹配的数量
	char fName[20];
	printf("1.根据学生姓名查找\n2.根据学生年龄查找\n请输入查找方式:");
	scanf("%d",&opt);
	switch (opt) {
		case 1:
			printf("请输入要查找的姓名:");
			scanf("%s",fName);
			while(p!=NULL){
				if(strcmp(p->name,fName)==0){
					printNode(p);
					n++;
				}
				p=p->next;
			}
			printf("共找到%d个匹配项;\n",n);
			break;
		case 2:
			printf("请输入要查找的年龄:");
			scanf("%d",&fAge);
			while (p != NULL) {
				if (p->age==fAge) {
					printNode(p);
					n++;
				}
				p = p->next;
			}
			printf("共找到%d个匹配项;\n", n);
			break;
		default:
			printf("错误!");
			return ;
			break;
	}
	return ;
}

void deleteNode(){
	if(amount==1){
		first=last=p=NULL;
		printf("删除成功!\n");
		return;
	}
	int n;								//删除的节点数
	printf("请输入要删除节点序数");
	getchar();
	scanf("%d",&n);
	p=returnNode(n);
	printNode(p);
	if(p==NULL){
		printf("错误!\n");
		return ;
	}
	if(p->prev==NULL){
		first=p->next;
		p->prev=NULL;
	}else if(p->next==NULL){
		last=p->prev;
		last->next=NULL;
	}else{
		p->prev->next=p->next;
		p->next->prev=p->prev;
	}
	printf("删除成功!\n");
}

/**
 * 返回第n个节点
 */
STU* returnNode(int n){
	p=first;
	if(n>amount||n<=0){
		printf("超过节点数 错误!");
		return NULL;
	}
	while(p!=NULL){
		n--;
		if(n==0){
			return p;
		}
		p=p->next;
	}
	return NULL;
}

/**
 * 插入节点
 */
void addNode(){
	p=first;
	int n;								//插入的节点数
	printf("请输入要插入节点序数");
	getchar();
	scanf("%d",&n);
	if(n>(amount+1)||n<=0){
		printf("超过节点数 错误!");
		return ;
	}
	p=(STU*)malloc(sizeof(STU));		//创造新的节点
	addInfo();
	STU* newNode=p;						//将newNode指向新建的节点
	if(n==amount+1){					//添加到链表末尾
		last->next=newNode;
		newNode->next=NULL;
		last=newNode;
		return ;
	}
	if(n==1){							//添加到链表表头
		newNode->next=first;
		newNode->prev=NULL;
		first=newNode;
		return ;
	}


	p=returnNode(n);
	if(p==NULL){
		printf("错误!");
		return ;
	}
										//插入到链表中部
	p->prev->next=newNode;
	newNode->prev=p->prev;
	p->prev=newNode;
	newNode->next=p;
	return ;
}
